package item08;

/**
 * @author Lv Jing
 * @date 2018年08月09日 23:06
 */
public class GetNext {

    /**
     * 面试题8：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
     * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
     * 思路：只有3种case，1）输入节点有右节点，那么下一个遍历节点为右节点的最左节点；
     * 2）输入节点无右节点，且是其父节点的左节点，那么下一个遍历节点就是其父节点；
     * 3）输入节点无右节点，且是其父节点的右节点，那么下一个遍历节点需要向上遍历，直到找到某一节点的父节点不是其右节点，或者其父节点为空；
     * 4）
     */
    public class Solution {
        public TreeLinkNode GetNext(TreeLinkNode pNode) {
            if (pNode == null) {
                return null;
            }

            TreeLinkNode temp;
            // 第一种case
            if (pNode.right != null) {
                temp = pNode.right;
                while (temp.left != null) {
                    temp = temp.left;
                }
                return temp;
            }
            // 第二种case
            temp = pNode;
            while (temp.next != null && temp.next.right == temp) {
                temp = temp.next;
            }
            return temp.next;
        }
    }

    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }
}
